//
//  AQSort.swift
//  AQAlgorithm
//
//  Created by zhangjikuan on 2020/8/26.
//  Copyright © 2020 hsgd. All rights reserved.
//

import Foundation


protocol AQSort {
    func sort(_ list:inout [Int]) -> Void

}

protocol AQArraySort {
    func sort<T: Comparable>(_ a: [T]) -> [T]
}


/// 冒泡排序
/// 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
/// 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
/// 针对所有的元素重复以上的步骤，除了最后一个。
/// 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
class AQBubbleSort: AQSort {
    func sort(_ list: inout [Int]) {
        for i in 0..<list.count - 1 {
            for j in 0..<list.count - 1 - i {
                if list[j] > list[j + 1] {
                    list.swapAt(j, j+1)
                }
            }
        }
    }
}

/// 选择排序
/// 选择排序（选择数组中最大的值或是最小的值然后放在最后一位或第一位)
class AQSelectionSort: AQSort {
    func sort(_ list: inout [Int]) {
        for j in 0..<list.count - 1 {
            var minIndex = j
            for i in j..<list.count {
                if list[minIndex] > list[i] {
                    minIndex = i
                }
            }
            list.swapAt(j, minIndex)
        }
    }
}

/// 插入排序
/// 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
/// 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
/// （如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
/// 类似于打扑克排序，， 打扑克的排序方式
/// 非常直观的排序方式
class AQInsertSort: AQSort {
    func sort(_ list: inout [Int]) {
        for i in 1..<list.endIndex {
            let temp = list[i]
            for j in (0..<i).reversed() {
                if list[j] > temp {
                    list.swapAt(j, j+1)
                }
            }
            
        }
        
    }
}


/// 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
/// 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
/// 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
/// 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
/// 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
class AQShellSort: AQSort {
    
    /// 插入排序算法
    /// - Parameters:
    ///   - list: 数组指针
    ///   - start: 开始索引
    ///   - gap: 步长
    func insertionSort(_ list: inout [Int], start: Int, gap: Int) {
        for i in stride(from: (start + gap), to: list.count, by: gap) {
            print(i)
            let currentValue = list[i]
            var pos = i
            while pos >= gap && list[pos - gap] > currentValue {
                list[pos] = list[pos - gap]
                pos -= gap
            }
            list[pos] = currentValue
        }
    }
    
    func sort(_ list: inout [Int]) {
        var sublistCount = list.count/2; /// [1,2,3,4,5,6,7,8,9,12] list.count = 10 sublistCount = list.count/2 = 5
        
        while sublistCount > 0 {
            for pos in 0..<sublistCount {
                insertionSort(&list, start: pos, gap: sublistCount)
            }
            sublistCount = sublistCount / 2
            
        }
        
        
    }
}

/// 归并排序， 二分法的思想  进行分而治之
class AQMergeSort:AQArraySort {
    func sort<T: Comparable>(_ array: [T]) -> [T] {
        guard array.count > 1 else { return array}
        let middleIndex = array.count / 2
        let leftArray = sort(Array( array[0..<middleIndex] ))
        let rightArray = sort(Array(array[middleIndex..<array.count]))
        return merge(leftPile: leftArray, rightPile: rightArray)
    }
    
    /// 合并到两个数组到一个数组
    func merge <T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] {
        var leftIndex = 0
        var rightIndex = 0
        var originPie = [T]()
        if originPie.capacity < leftPile.count + rightPile.count {
            originPie.reserveCapacity(leftPile.count + rightPile.count)
        }
        
        while true {
            guard leftIndex < leftPile.endIndex else {
                originPie.append(contentsOf: rightPile[rightIndex..<rightPile.endIndex])
                break
            }
            guard rightIndex < rightPile.endIndex else {
                originPie.append(contentsOf: leftPile[leftIndex..<leftPile.endIndex])
                break
            }
            if leftPile[leftIndex] < rightPile[rightIndex] {
                originPie.append(leftPile[leftIndex])
                leftIndex += 1
            } else {
                originPie.append(rightPile[rightIndex])
                rightIndex += 1
            }
        }
        
        return originPie
    }
}

/// 快速排序 也是 分而治之的算法思想的一种应用，中间采用了低估的一种算法方式
/// 最优时间复杂度为O( nlogn) 最坏为O(n^2)
/// 最坏的发生概率很小 相比归并排序显得更加高效
class AQQuikSort: AQArraySort {
    func sort<T>(_ a: [T]) -> [T] where T : Comparable {
        guard a.count > 1 else {
            return a
        }
        let pivot = a[a.count/2]
        /// filter 属性相当的厉害
        
        let less = a.filter{ $0 < pivot }
        let equal = a.filter{ $0 == pivot }
        let greater = a.filter({ $0 > pivot})
        return sort(less) + equal + sort(greater)
    }
}

/// 堆排序 堆排序 堆一种特殊的二叉树  树型结构
protocol AQHeapSort {
   func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T]
}

extension AQHeapSort {
    func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T] {
        let reverseOrder = { i1, i2 in sort(i2, i1) }
        var h = Heap(array: a, sort: reverseOrder)
        return h.sort()
    }
}

